package com.xiyou.week01.linked;


/**
 * 141. 环形链表
 *
 * @ClassName：LeetCode141
 * @Author：西柚
 * @Date：2021/11/20 3:02 下午
 * @Versiion：1.0
 */
public class HasCycle {

    /**
     * 输入：head = [3,2,0,-4], pos = 1
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第二个节点。
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next; // 快指针，一次移动两步
            head = head.next;       // 慢指针，一次移动一步
            if (fast == head) {     // 快慢指针相遇，表明有环
                return true;
            }
        }
        return false;               // 正常走到链表末尾，表明没有环
    }

    public static void main(String[] args) {
        ListNode nodeSta = new ListNode(3);    //创建首节点
        ListNode nextNode;                     //声明一个变量用来在移动过程中指向当前节点
        nextNode = nodeSta;                      //指向首节点

        //创建链表
        ListNode node = new ListNode(2);  //生成新的节点
        nextNode.next = node;               //把心节点连起来
        nextNode = nextNode.next;           //当前节点往后移动

        node = new ListNode(0);        //生成新的节点
        nextNode.next = node;               //把心节点连起来
        nextNode = nextNode.next;           //当前节点往后移动

        node = new ListNode(-4);        //生成新的节点
        nextNode.next = node;               //把心节点连起来
        nextNode = nextNode.next;           //当前节点往后移动

//        nextNode = nodeSta;                   //重新赋值让它指向首节点
        print(nodeSta);                      //打印输出

        HasCycle leetCode141 = new HasCycle();
        System.out.println(leetCode141.hasCycle(nodeSta));

    }

    //打印输出方法
    static void print(ListNode listNoed) {
        //创建链表节点
        while (listNoed != null) {
            System.out.println("节点:" + listNoed.val);
            listNoed = listNoed.next;
        }
        System.out.println();
    }

}
